
import InnerInterface.Student;

import java.util.*;
import java.util.concurrent.PriorityBlockingQueue;

public class test1 {
	static List<String> ans=new ArrayList<>();
	static StringBuffer stringBuffer=new StringBuffer();

	static  int [] dx={1,-1,0,0};
	static  int [] dy={0,0,1,-1};
	static class Student{
		String name;
	}

	private static String rearrangeToEven(int num) {

		// 如果本身就是偶数，直接返回
		if (num % 2 == 0) {
			return String.valueOf(num);
		}

		char[] digits = String.valueOf(num).toCharArray();
		int n = digits.length;

		// 从右向左找第一个偶数数字
		int lastEvenIndex = -1;
		for (int i = n - 1; i >= 0; i--) {
			if ((digits[i] - '0') % 2 == 0) {
				lastEvenIndex = i;
				break;
			}
		}

		// 如果没有偶数数字，返回-1
		if (lastEvenIndex == -1) {
			return "-1";
		}

		// 交换最后一个数字和找到的偶数数字
		swap(digits, lastEvenIndex, n - 1);

		// 检查是否有前导零
		if (digits[0] == '0') {
			// 如果有前导零，需要找到下一个可交换的偶数
			for (int i = 1; i < n - 1; i++) {
				if ((digits[i] - '0') % 2 == 0) {
					swap(digits, i, n - 1);
					// 再次检查前导零
					if (digits[0] == '0') {
						continue; // 继续寻找
					} else {
						break; // 找到有效交换
					}
				}
			}

			// 如果仍有前导零，返回-1
			if (digits[0] == '0') {
				return "-1";
			}
		}

		return new String(digits);
	}

	private static void swap(char[] arr, int i, int j) {
		char temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	public static void main80(String[] args) {

		System.out.println("HELLO WORLD");
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		long[] nums = new long[n];
		for (int i = 0; i < n; i++) {
			nums[i] = in.nextLong();
		}

		long include = nums[0];
		long exclude = 0;

		for (int i = 1; i < n; i++) {
			long newInclude = exclude + nums[i];
			long newExclude = Math.max(include, exclude);

			include = newInclude;
			exclude = newExclude;
		}

		System.out.println(Math.max(include, exclude));
	}
	public static void main79(String[] args) {
		ArrayList<ArrayList<Integer>> list =new ArrayList<>();
		ArrayList<Integer> row1 = new ArrayList<>();
		row1.add(1);
		row1.add(1);
		row1.add(0);
		list.add(row1);

		// 初始化第二个子列表 {1, 1, 0}
		ArrayList<Integer> row2 = new ArrayList<>();
		row2.add(1);
		row2.add(1);
		row2.add(0);
		list.add(row2);

		// 初始化第三个子列表 {0, 0, 1}
		ArrayList<Integer> row3 = new ArrayList<>();
		row3.add(0);
		row3.add(0);
		row3.add(1);
		list.add(row3);
		int rows = list.size();
		int cols = list.get(0).size();
		int [][] nums = new int[rows][cols];
		for(int i =0;i<list.size();i++) {
			for(int j =0;j<cols;j++) {
				nums[i][j]=list.get(i).get(j);
			}
		}
		int ret = 0;
		boolean [] [] hash = new boolean[rows][cols];
		Queue<int[]> queue = new LinkedList<>();
		for (int i = 0; i < rows; i++) {
			for (int j = 0; j < cols; j++) {
				if (nums[i][j] == 1 && hash[i][j] == false) {
					queue.offer(new int[]{i, j});
					hash[i][j] = true;
					while (!queue.isEmpty()) {
						int size = queue.size();
						while (size-- > 0) {
							int[] temp = queue.poll();
							for (int k = 0; k < 4; k++) {
								int row = temp[0] + dx[k];
								int col = temp[1] + dy[k];
								if (row >= 0 && row < rows && col >= 0 && col < cols && !hash[row][col] &&
										nums[row][col] == 1) {
									queue.offer(new int[]{row, col});
									hash[row][col] = true;
								}
							}
						}
					}
					ret++;
				}
			}
		}
		System.out.println(ret);
	}

	public static void main78(String[] args) {
		ArrayList<ArrayList<Integer>> list = new ArrayList<>();
		Map<String,Integer> map=new HashMap<>();
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		while(n-->0) {
			int ret = 0;
			int  h = in.nextInt();
			int  a = in.nextInt();
			int H = in.nextInt();
			int A = in.nextInt();
			if(a>=H) {
				System.out.println(-1);
				continue;
			}
			int temp = H;
			while(h>0) {
				if(H<=0) {
					H=temp;
				}
				H-=a;
				if(H<=0) {
					ret++;
				}
				h-=A;
			}
			System.out.println(ret);
		}
	}

	public static void main77(String[] args) {
		char [] nums1 = new char[] {'a','b','e'};
		char [] nums2 = new char[] {'c','a','b','c'};

		int len = nums2.length-nums1.length;//差的长度

		int ret = nums1.length;

		for(int i =0;i<=len;i++) {
			int temp=0;
			for(int j =0;j<nums1.length;j++) {
				if(nums1[j]!=nums2[i+j]) {
					temp++;
				}
			}
			ret = Math.min(temp,ret);
		}
		System.out.println(ret);
		System.out.printf("%c",ret);
	}

	public static void main76(String[] args) {
		int len1 =2;
		int len2 = 2;
		int [] nums1 = new int[]{1,2};
		int [] nums2 = new int[]{1,2};
		int k =0;
		int [] nums = new int [len1+len2];
		int i=0,j=0;
		while(i<len1 && j<len2) {
			if(nums1[i]<nums2[j]) {
				nums[k++]=nums1[i++];
			} else {
				if(nums1[i]==nums2[j]) {
					nums[k++]=nums1[i];
					i++;
					j++;
					continue;
				} else {
					nums[k++]=nums2[j++];
				}
			}
		}
		if(i<len1) {
			while(i<len1) {
				nums[k++]=nums1[i++];
			}
		}
		if(j<len2) {
			while(j<len2) {
				nums[k++]=nums2[j++];
			}
		}
		for(int index = 0;index<nums.length;index++) {
			if(index<nums.length && nums[index]!=0) {
				System.out.print(nums[index]+" ");
			}
		}
	}

	public static void main75(String[] args) {
		//最长非回文字符串
		Scanner in=new Scanner(System.in);
		char [] nums = in.next().toCharArray();
		int length = nums.length;

		boolean flag = false;
		//这个情况是针对一个都是一样字符的字符串来说的
		for(int i =1;i<length;i++) {
			if(nums[i]!=nums[0]) {
				flag = true;
				break;
			}
		}
		if(flag) {
			//针对不同字符的字符串来说的
			flag = false;
			int left=0,right=length-1;
			while(left<right) {
				if(nums[left]==nums[right]) {
					left++;
					right--;
				} else {
					flag = true;
					break;
				}
			}
			if(flag) {
				System.out.println(length);
			} else {
				System.out.println(length-1);
			}
		} else {
			System.out.println(0);
		}
	}

	public static void main74(String[] args) {
		int a = 2;
		int h = 3;//对立的血量
		int b = 1;//光的攻击
		int k = 3;//光的血量

		long sum =0;//小红受到的伤害

		while(true) {
			sum+=b;
			sum+=a;
			//此时开始同时攻击
			h-=b;
			k-=a;
			if(h==0) {
				sum+=10*b;
				break;
			}
			if(k==0) {
				sum+=10*a;
				break;
			}
		}
		System.out.println(sum);
	}

	public static void main73(String[] args) {
		int [][] nums = new int[][]{{1,3,1},{1,5,1},{4,2,1}};
		int sum = 0;
		int rows = nums.length,cols = nums[0].length;
		int i=0,j=0;
		sum+=nums[i][j];
		while(i<=rows-1 && j<=cols-1) {
			int num1 = -1;
			//先算右边
			if(j+1<cols) {
				num1 = nums[i][j+1];
			}
			int num2 = -1;
			if(i+1<rows) {
				num2 = nums[i+1][j];
			}
			sum+=Math.max(num1,num2);
			if(num1>num2) {
				j++;
			} else {
				i++;
			}
			if(i==rows-1 && j==cols-1) {
				break;
			}
		}
		System.out.println(sum);
	}

	public static void main72(String[] args) {
		System.out.println("hello world");
		System.out.println("hello world");
		System.out.println("hello world");
		PriorityQueue<int []> queue = new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[1]!=o2[1]) {
					return o2[1]-o1[1];
				} else {
					return o1[0]-o2[0];
				}
			}
		});
	}
	public static void main71(String[] args) {
		System.out.println("hello world");
		String str = "aaaaa";
		int num=5;
		char [] nums = new char[num];

		Map<Character,Integer> hash = new HashMap<>();

		for(int i=0;i<str.length();i++) {
			char ch = str.charAt(i);
			hash.put(ch,hash.getOrDefault(ch,0)+1);
		}
		int k =0;
		PriorityQueue<Map.Entry<Character,Integer>> queue = new PriorityQueue<>((a,b)->b.getValue()-a.getValue());
		for(Map.Entry<Character,Integer> entry:hash.entrySet()) {
			queue.offer(entry);
		}
		while(!queue.isEmpty()) {
			Map.Entry<Character, Integer> entry = queue.poll();
			if(entry.getValue()>num/2) {
				System.out.println("no");
				return ;
			}
			for(int i =0;i<entry.getValue();i++) {

				nums[k]=entry.getKey();
				k+=2;
				if(k>=nums.length) {
					k=1;
				}
			}
		}
		System.out.println("yes");
		System.out.println(Arrays.toString(nums));
	}

	public static void main70(String[] args) {
		Map<Character,Integer> hash1 = new HashMap<>();
		Collection<Integer> values = hash1.values();
		Set<Character> set = hash1.keySet();
		int [] nums = new int[] {1,2,3,1,2,3,2,2};
		Set<Integer> hash = new HashSet<>();
		int length=0,left=0;
		for(int i =0;i<nums.length;i++) {
			if(!hash.contains(nums[i])) {
				hash.add(nums[i]);
				length++;
			} else {
				hash = new HashSet<>();
				hash.add(nums[i]);
				length = Math.max(length,i-left);
				left=i;
			}
		}
	}

	public static void main69(String[] args) {
		int n =4,k=5;
		int [] a=new int[]{3,5,1,7,1,7};
		int [] b=new int[]{4,6,5,1,5,1};
		for(int i=n-2;i>=0;i--){
			a[i]+=a[i+1];
			b[i]+=b[i+1];
		}
		long max = 0;//最大快乐值
		long min = Integer.MAX_VALUE;//最小羞耻值
		int ret = 0;
		for(int i=0;i<n;i++){
			if(i+k<n){
				a[i] -=a[i+k];
				b[i] -=b[i+k];
			}
			if(max<a[i]){
				ret = i;
				max = a[i];
			}else if(max==a[i] && min>b[i]){
				min = b[i];
				ret = i;
			}
		}
		System.out.println(ret+1);
	}
	public static void main68(String[] args) {
		dfs2(3,0,0);
		System.out.println(ans.toString());
		System.out.println();

	}
	public static void  dfs2(int num,int open,int close) {
		if(stringBuffer.length()>=num*2) {
			ans.add(stringBuffer.toString());
			return ;
		}
		if(open<num) {
			stringBuffer.append('(');
			open+=1;
			dfs2(num,open,close);
			stringBuffer.setLength(stringBuffer.length()-1);
		}
		if(close<=open) {
			stringBuffer.append(')');
			close+=1;
			dfs2(num,open,close);
			stringBuffer.setLength(stringBuffer.length()-1);
		}
	}
	public static void main67(String[] args) {
		System.out.println("hello world");
		List<String > ans=new ArrayList<>();
		List<Character> list=new ArrayList<>();
		list.add('a');
		list.add('b');
		list.add('c');
		System.out.println(list.toString());
		StringBuffer sb=new StringBuffer();
		sb.append('a');
		sb.setLength(sb.length()-1);
		ans.add(list.toString());
	}
	static List<List<Integer>>ans2=new ArrayList<>();
	static List<Integer> list=new ArrayList<>();
//	public static void dfs(int [] nums,int pos) {
//		if(pos>=nums.length) {
//			ans.add(list);
//			return ;
//		}
//		//这里面临选或者是不选的问题
//		list.add(nums[pos]);
//		dfs(nums,pos+1);
//		list.remove(list.size()-1);
//		dfs(nums,pos+1);
//	}
	static List<List<Integer>> ans1=new ArrayList<>();
	static List<Integer> list1 = new ArrayList<>();
	static  boolean[] used;

	public static void main64(String[] args) {
		StringBuffer stringBuffer=new StringBuffer();
		String str=new String();
		String str1="->";
	}
	public static void main63(String[] args) {
		int num=2,n=-2;
		double temp = dfs(num, n);
		System.out.println(temp);
	}
	public static double  dfs(double num,int n) {
		if(n==0) {
			return 1;
		}
		double temp=dfs(num,n/2);
		return n%2==1? temp*temp*num:temp*temp;
	}
	public static void main62(String[] args) {
		List<Integer> list1=new ArrayList<>();
		list1.add(3);
		list1.add(2);
		list1.add(1);
		List<Integer> list2=new ArrayList<>();
		List<Integer> list3=new ArrayList<>();
		dfs1(list1,list2,list3,list1.size());
	}
	public static void dfs1(List<Integer> list1, List<Integer> list2, List<Integer> list3,int num) {
		if(num==1) {
			list3.add(list1.get(list1.size()-1));
			list1.remove(list1.size()-1);
			return ;
		}
		dfs1(list1,list3,list2,num-1);
		//当上面第一个移过之后
		list3.add(list1.get(list1.size()-1));
		list1.remove(list1.size()-1);

		dfs1(list2,list1,list3,num-1);
	}
	public static void main61(String[] args) {
		int [] nums=new int[]{1,2,3,4,5};
		int [] ans=new int[nums.length];
		Map<Integer,Integer> map=new HashMap<>();
		for(int num:nums) {
			map.put(num,map.getOrDefault(num,0)+1);
		}

		List<Map.Entry<Integer,Integer>> list=new ArrayList<>(map.entrySet());
		Collections.sort(list,(e1,e2)->e2.getValue()-e1.getValue());
		int [] temp=new int[list.size()];
		for(int i=0;i<list.size();i++) {
			temp[i]=list.get(i).getValue();
		}
		int len=nums.length;
		int j=0;
		for(int i=0;i<len;i+=2) {
			ans[i]=list.get(j).getKey();
			temp[j]--;
			if(temp[j]==0) {
				j++;
			}
		}
		for(int i=1;i<len;i+=2) {
			ans[i]=list.get(j).getKey();
			temp[j]--;
			if(temp[j]==0) {
				j++;
			}
		}
	}
	public static void main60(String[] args) {
		int [] nums={5,2,2,2};
		Arrays.sort(nums);
		int sum=0;
		List<Integer> list1=new ArrayList<>();
		List<Integer> list2=new ArrayList<>();
		Collections.sort(list1,(a,b)->a-b);

		Collections.sort(list2,(a,b)->a-b);
		for(int i =0;i<nums.length;i++) {
			sum+=nums[i];
			if(nums[i]%3==1) {
				list1.add(nums[i]);
			} else if(nums[i]%3==2) {
				list2.add(nums[i]);
			}
		}
		if(sum%3!=0 && nums.length==1) {
			return ;
		}
		while(sum%3!=0) {
			if(sum%3==1) {
				int num1=Integer.MAX_VALUE,num2=Integer.MAX_VALUE;
				if(list1.size()>0) {
					num1=list1.get(0);
				}
				if(list2.size()>1 && (list2.get(0)+list2.get(1))%3==1) {
					num2=list2.get(0)+list2.get(1);
				}
				sum=Math.max(sum-num1,sum-num2);
				if(num1>num2) {
					list2.remove(0);
					list2.remove(0);
				} else {
					list1.remove(0);
				}
			} else {
				int num1=Integer.MAX_VALUE,num2=Integer.MAX_VALUE;
				if(list1.size()>1 && (list1.get(0)+list1.get(1))%3==2){
					num1=list1.get(0)+list1.get(1);
				}
				if(list2.size()>0) {
					num2=list2.get(0);
				}
				sum=Math.max(sum-num1,sum-num2);
				if(num1>num2) {
					list2.remove(0);
				} else {
					list1.remove(0);
					list1.remove(0);
				}
			}
		}
		System.out.println(sum);
	}
	public static void main59(String[] args) {
		int [] [] nums=new int[][]{{4,5},{4,6},{6,7},{2,3},{1,1}};
		List<int[]> list=new ArrayList<>();
		int len=nums.length;
		Arrays.sort(nums,new Comparator<int[]>() {
			public int compare(int[] o1, int[] o2) {
				if(o1[0]!=o2[0]) {
					return o1[0]-o2[0];
				} else {
					return o2[1]-o1[1];
				}
			}
		});
		int index=0;
		while(index<len) {
			int num1=nums[index][0],num2=nums[index][1];
			if(list.size()==0 || num2>list.get(list.size()-1)[1]) {
				list.add(new int [] {num1,num2});
			} else {
				//这里就要寻找位置了
				int left=0,right=list.size()-1;
				while(left<right) {
					int mid=(right-left)/2+left;
					//寻找左端点
					if(list.get(mid)[1]<num2) {
						left=mid+1;
					} else {
						right=mid;
					}
				}
				list.remove(left);
				list.add(left,new int[]{num1,num2});
			}
			index++;
		}
	}
	public static void main58(String[] args) {
		int n=65535;
		int result=1;
		int ans=0;
		while(result!=n) {
			if(n%2==0) {
				n/=2;
				ans++;
			} else {
				if(n>result) {
					n-=1;
				} else {
					n+=1;
				}
				ans++;
			}
		}
	}
	public static void main57(String[] args) {
		char ch='a';
		Character.isLowerCase(ch);
		//nums1 = [2,7,11,15], nums2 = [1,10,4,11]
		int [] nums1={12,24,8,32};
		int [] nums2={13,25,32,11};
		int len=nums1.length;
		int [] ret=new int[len];//结果返回的数组
		Integer[] index1=new Integer[len];//对下标排序
		Integer[] index2=new Integer[len];//对下标排序

		Arrays.sort(nums1);
		for(int i =0;i<len;i++) {
			index1[i]=i;
			index2[i]=i;
		}
		Arrays.sort(index1,(num1,num2)->nums1[num1]-nums1[num2]);
		Arrays.sort(index2,(num1,num2)->nums2[num1]-nums2[num2]);

		int left=0,right=len-1;
		//遍历nums1数组
		for(int i =0;i<len;i++) {
			if(nums1[index1[i]]>=nums2[index2[i]]) {
				ret[left]=nums1[index1[i]];
				left++;
			} else {
				ret[index2[right]]=nums1[index1[i]];
				right--;
			}
		}
	}
	public static void main56(String[] args) {
		int [] nums={0,1,2,3,4,5,6,7,8,9};

		System.out.println(nums.toString());
	}
	public static void main55(String[] args) {
		int [] nums={2,4,3};
		int k=1;
		int count=0;
		for(int num:nums) {
			if(num<0) {
				count++;
			}
		}
		Arrays.sort(nums);
		int sum=0;
		int times=0;
		if(count==0) {
			for(int i =0;i<nums.length;i++) {
				if(i<k) {
					sum+=(-nums[i]);
				} else {
					sum+=nums[i];
				}
			}
		} else if(count>k) {
			for(int i =0;i<nums.length;i++) {
				if(times<k) {
					sum+=Math.abs(nums[i]);
					times++;
				} else {
					sum+=nums[i];
				}
			}
		} else if(count<=k) {
			for(int i=0;i<nums.length;i++) {
				sum+=Math.abs(nums[i]);
			}
		}
		System.out.println(sum);
	}
	public static void main54(String[] args) {
		int[] nums={1,3,5,4,7};
		int cur=0,ans=0;
		boolean flag=false;
		for(int i=0;i<nums.length;) {
			while(cur+1<nums.length && nums[cur+1]>nums[cur]) {
				cur++;
				flag=true;
			}
			if(flag) {
				ans=Math.max(ans,cur-i+1);
				flag=false;
				i=cur+1;
			}
		}
	}

	public static void main53(String[] args) {
		List<Integer> list=new ArrayList<>();
		int [] nums={0,1,0,3,2,3};
		int len=nums.length;
		for(int num:nums) {
			if(list.size()==0) {
				list.add(num);
			} else {
				if(num>list.get(list.size()-1)) {
					list.add(num);
				} else {
					int left=0,right=list.size()-1;
					while(left<right) {
						int mid=left+(right-left)/2;
						if(list.get(mid)<num) {
							left=mid+1;
						} else {
							right=mid;
						}
					}
					list.remove(left);
					list.add(left,num);
				}
			}
		}
		System.out.println(list.size());
	}
	public static void main52(String[] args) {
		int []nums={18,22,62,61,1,88,17,98,38,32,51,57,7,29,40,61,62,13,89,41,73,85,88,60,59,76,71,76,76,41,29,43,19,9,79};
		PriorityQueue<Double> queue=new PriorityQueue<>((o1,o2)->Double.compare(o2,o1));
		double sum=0;
		for(int num:nums) {
			sum+=(double) num;
			queue.offer((double)num);
		}
		double mid=(double)sum/2;

		int ret=0;
		while(!queue.isEmpty()) {
			ret++;
			double temp=queue.poll();
			queue.offer(temp/2);
			sum-=(temp/2);
			if(sum<=mid) {
				break;
			}
		}
		System.out.println(ret);
		StringBuffer sb=new StringBuffer();
	}
	public static void main51(String[] args) {
		int [] nums={10,4,8,9,201,202};
		PriorityQueue<Integer > queue=new PriorityQueue<>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				String str1=String.valueOf(o1);
				String str2=String.valueOf(o2);
				String str3=new String(str1+str2);
				String str4=new String(str2+str1);
				return str4.compareTo(str3);
			}
		});
		for(int num:nums) {
			queue.offer(num);
		}
		while(!queue.isEmpty()) {
			System.out.println(queue.poll());
		}
	}
	public static void main50(String[] args) {
		String [] words={"wrt","wrf","er","ett","rftt"};
		Map<String,Integer> hash2=new HashMap<>();
		Map<Character,Integer> count=new HashMap<>();//统计入度的信息

		for(String temp:words) {
			hash2.put(temp,hash2.getOrDefault(temp,0)+1);
			for(int i=0;i<temp.length();i++) {
				count.put(temp.charAt(i),0);
			}
		}
		for(int x:hash2.values()) {
			if(x>1) {
				System.out.println("15行出错");
			}
		}
		Map<Character,Set<Character>> hash=new HashMap<>();//创建图
		StringBuffer stringBuffer=new StringBuffer();
		int len=words.length;
		//先进行搜集信息
		for(int i=0;i<len;i++) {
			for(int j=i+1;j<len;j++) {
				String str1=words[i],str2=words[j];
				int len1 = Math.min(str1.length(),str2.length());
				for(int cur=0;cur<len1;cur++) {
					if(cur==len1-1 && str1.charAt(cur)==str2.charAt(cur)) {
						System.out.println("29行出错");
					}
					char ch1=str1.charAt(cur),ch2=str2.charAt(cur);
					if(ch1!=ch2) {
						//这里进行添加元素
						if(!hash.containsKey(ch1)) {
							hash.put(ch1,new HashSet<>());
						}
						if(!hash.get(ch1).contains(ch2)) {
							hash.get(ch1).add(ch2);
							count.put(ch2,count.get(ch2)+1);
						}
						break;
					}
				}
			}
		}
		Queue<Character> queue=new LinkedList<>();
		//进行遍历count哈希
		for(Map.Entry<Character,Integer> entry:count.entrySet()) {

			if(entry.getValue()==0) {
				queue.offer(entry.getKey());
			}
		}
		while(!queue.isEmpty()) {
			char ch=queue.poll();
			stringBuffer.append(ch);
			if(!hash.containsKey(ch)) {
				continue;
			}
			for(char ch1:hash.get(ch)) {
				count.put(ch1,count.get(ch1)-1);
				if(count.get(ch1)==0) {
					queue.offer(ch1);
				}
			}
		}
		System.out.println(stringBuffer.toString());
	}
	public static void main49(String[] args) {
		PriorityQueue<Map.Entry<String,Integer>> queue=new PriorityQueue<>(((o1, o2) -> {
			if (o1.getValue() == o2.getValue()) {
				return o2.getKey().compareTo(o1.getKey());
			}
			return o1.getValue()-o2.getValue();
		}));
		Map<String,Integer> map=new HashMap<>();
		String[] nums={"i", "love", "leetcode", "i", "love", "coding"};
		for(String str:nums) {
			map.put(str,map.getOrDefault(str,0)+1);
		}
		for(Map.Entry<String,Integer> entry:map.entrySet()) {
			if(queue.size()<2) {
				queue.add(entry);
			} else {
				if(queue.peek().getValue()<entry.getValue() || queue.peek().getKey().compareTo(entry.getKey())<0) {
					queue.poll();
					queue.add(entry);
				}
			}
		}
		while(!queue.isEmpty()) {
			Map.Entry<String,Integer> entry=queue.poll();
			System.out.println(entry.getKey()+" "+entry.getValue());
		}
	}
	public static void main48(String[] args) {
		String s="y#fo##f";
		String t="y#f#o##f";
		Stack<Character> st1=new Stack<>();
		Stack<Character> st2=new Stack<>();
		for(int i =0;i<s.length();i++) {
			char ch1=s.charAt(i);
			if(ch1=='#') {
				if(!st1.isEmpty()) {
					st1.pop();
				}
			} else {
				st1.push(ch1);
			}
		}
		for(int i =0;i<t.length();i++) {
			char ch1=t.charAt(i);
			if( ch1=='#') {
				if(!st2.isEmpty()) {
					st2.pop();
				}
			} else {
				st2.push(ch1);
			}
		}
		System.out.println(st1.equals(st2));
	}
	public static void main45(String[] args) {
		String nums1="1010";
		String nums2="1011";
		int cur1=nums1.length()-1;
		int cur2=nums2.length()-1;
		int parse=0;
		StringBuffer stringBuffer = new StringBuffer();
		while(cur1>=0 || cur2>=0) {
			int num1=0;
			int num2=0;
			if(cur1>=0) {
				num1=nums1.charAt(cur1)-'0';
			}
			if(cur2>=0) {
				num2=nums2.charAt(cur2)-'0';
			}
			int sum=(num1+num2);
			stringBuffer.append((sum+parse)%2);
			parse=(sum+parse)/2;
			cur1--;
			cur2--;
		}
		if(parse==1) {
			stringBuffer.append(parse);
		}
		System.out.println(stringBuffer.reverse().toString());
	}

	public static void main44(String[] args) {
		int num=1;
		String value = String.valueOf(num);
		System.out.println(value);

	}
	public static void main43(String[] args) {
		Map<Integer,Integer> map=new HashMap<>();
	}
	public static class ListNode { int val;
     ListNode next;
     ListNode() {}
      ListNode(int val) { this.val = val; }
		ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
	public static void main42(String[] args) {
		int n=1;
		ListNode head = new ListNode(1);
		head.next = new ListNode(2);
		List<ListNode> list=new ArrayList<>();
		ListNode cur=head;
		while(cur!=null) {
			list.add(cur);
			cur=cur.next;
		}
		ListNode phead=new ListNode();
		cur=phead;
		int len=list.size();
		list.remove(list.size()-n);
		for(int i=0;i<len;i++) {
			cur.next=list.get(i);
			cur=cur.next;
		}
		System.out.println(list.toString());
	}
	public static void main41(String[] args) {
		int [][] nums=new int[3][3];
		nums[0][0]=1;
		nums[0][1]=2;
		nums[0][2]=3;
		nums[1][0]=4;
		nums[1][1]=5;
		nums[1][2]=6;
		Arrays.sort(nums,new Comparator<int[]>() {
			public int compare(int[] o1, int[] o2) {
				//升序的一个作用
				return o1[0]-o2[0];
			}
		});
	}
	public static void main40(String[] args) {
		String[] strs = new String[]{"eat", "tea", "tan", "ate", "nat", "bat"};
		String num= strs[0];
		char [] ch= num.toCharArray();
		Arrays.sort(ch);
		String str = new String(ch);
	}
	public static void main39(String[] args) {
		int [] nums=new int[]{-4,-1,-1,0,1,2};
		List<List<Integer>> list=new ArrayList<>();
		for(int i=0;i<nums.length;) {
			if(nums[i]>0) {
				break;
			}
			List<Integer> newList=new ArrayList<>();
			int left=i+1,right=nums.length-1,k=-nums[i];
			while(left<right) {
				int sum=nums[left]+nums[right];
				if(sum>k) {
					right--;
				}else if(sum<k) {
					left++;
				} else {
					list.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));
					left++;
					right--;
					//这里还得去重
					while(left<right && nums[left]==nums[left-1]) left++;
					while(left<right && nums[right]==nums[right+1]) right--;
				}
			}
			i++;
			while(i<nums.length && nums[i]==nums[i-1]) i++;
		}
		Collections.reverse(list);
	}
	public static void main38(String[] args) {
		int [] nums=new int[]{100,200,300,400,500,600,700,800,900,1000};
		List<Integer> list=new ArrayList<>();
		List<Integer> list1=new ArrayList<>();
		list1.add(12222);
		list.addAll(list1);
		System.out.println(list);
		Runnable runnable=new Runnable() {
			@Override
			public void run() {
				System.out.println("开始打印线程");
			}
		};
		runnable.run();
		Thread t1=new Thread(()->{
			while(true) {
				System.out.println("hello 新线程");
				try{
					Thread.sleep(1000);
				}catch (Exception e) {
					e.printStackTrace();
				}
			}
		},"新线程");
		t1.run();
		StringBuilder stringBuilder=new StringBuilder();
		String str="abc";
		char[] charArray = str.toCharArray();
		stringBuilder.reverse().toString();
		Stack<Character> stack=new Stack<>();
		stack.pop();
		List<Integer> list2=new ArrayList<>();
	}
	public static void main37(String[] args) {
		String str="IVXLCDM";
		String s="MCMXCIV";
		Map<Character,Integer> map=new HashMap<>();
		for(int i =0;i<str.length();i++) {
			char ch=str.charAt(i);
			if(ch=='I') {
				map.put(ch,1);
			} else if(ch=='V') {
				map.put(ch,5);
			} else if(ch=='X') {
				map.put(ch,10);
			} else if(ch=='L') {
				map.put(ch,50);
			} else if(ch=='C') {
				map.put(ch,100);
			} else if(ch=='D') {
				map.put(ch,500);
			} else if(ch=='M') {
				map.put(ch,1000);
			}
		}
		//处理特殊情况
		int ret=0,i=0,num=0;
		while(i<s.length()) {
			if(map.get(s.charAt(i))>num) {
				ret-=num;
				ret+=(map.get(s.charAt(i))-num);
			} else {
				ret+=map.get(s.charAt(i));
			}
			char ch=s.charAt(i);
			num=map.get(ch);
			i++;
		}
		System.out.println(ret);
	}
	//关于快速排序的话，直接使用一个三路划分

	public static void main35(String[] args) {
		int [] nums=new int[]{10,5,7,3,8,9,100,200,444};
		//mergeFunc(nums,0,nums.length-1);
		qsort(nums,0,nums.length-1);
		System.out.println(Arrays.toString(nums));
	}
	public static void qsort(int [] nums,int l, int r){
		//条件很重要
		if(l>r) {
			return ;
		}
		//首先快速排序的话，先有一个中间值
		int left=l-1,right=r+1,i=l;
		int key=nums[new Random().nextInt(r-l+1)+l];
		while(i<right) {
			if(nums[i]==key) {
				i++;
			} else if(nums[i]>key) {
				swap(nums,i,--right);
			} else {
				swap(nums,++left,i++);
			}
		}
		qsort(nums,l, left);
		qsort(nums,right,r);
	}
	//归并排序
	private static void mergeFunc(int[] nums,int left,int right) {
		if(left>=right) {
			return ;
		}
		int mid=(right+left)/2;
		mergeFunc(nums,left,mid);
		mergeFunc(nums,mid+1,right);
		merge(nums,left,right,mid);
	}
	public static void merge(int[] nums,int left,int right,int mid) {
		int s1=left;
		int s2=mid+1;
		int [] tempNums=new int[right-left+1];
		int k=0;
		//小的尾插
		while(s1<=mid && s2<=right) {
			if(nums[s1]<=nums[s2]) {
				tempNums[k++]=nums[s1++];
			} else {
				tempNums[k++]= nums[s2++];
			}
		}
		//判断数组是不是没有了
		while(s1<=mid) {
			tempNums[k++]=nums[s1++];
		}
		while(s2<=right) {
			tempNums[k++]= nums[s2++];
		}
		//拷贝回原数组
		for(int i=0;i<tempNums.length;i++) {
			nums[left+i]=tempNums[i];
		}
	}
	public static void main34(String[] args) {
		int [] nums=new int[]{10,5,7,3,8,9,100,200,444};
		//堆排序
		createHeap(nums);
		int end=nums.length-1;
		//end是边界，如果等于零的话，在最后面的话 ，	[-1, end(0)] 会造成越界
		while(end>0) {
			swap(nums,0,end);
			siftDown(nums,0,end);
			end--;
		}
		System.out.println(Arrays.toString(nums));
	}
	public static void createHeap(int [] nums) {
		for(int parent=(nums.length-1-1)/2; parent>=0; parent--) {
			siftDown(nums,parent,nums.length);
		}
	}
	public static void siftDown(int [] nums,int parent,int end) {
		int child=parent*2+1;
		while(child<end) {
			if(child+1<end && nums[child]<nums[child+1]) {
				child++;
			}
			if(nums[child]>nums[parent]) {
				swap(nums,parent,child);
				parent=child;
				child=parent*2+1;
			} else {
				break;
			}
		}
	}
	public static void selectSort1(int[] nums) {
		int left=0,right=nums.length-1;
		while(left<right) {
			int minindex=left;
			int maxindex=right;
			for (int i =left+1;i<right;i++) {
				if(nums[i]<nums[minindex]) {
					minindex=i;
				}
				if(nums[i]>nums[maxindex]) {
					maxindex=i;
				}
			}
			swap(nums,left,minindex);
			//如果最大在最左边的话 ，最大值的位置就跑了
			if(maxindex==left) {
				maxindex=minindex;
			}
			swap(nums,right,maxindex);
			left++;
			right--;
		}
	}
	public static void swap(int[] nums,int i,int j) {
		int temp=nums[i];
		nums[i]=nums[j];
		nums[j]=temp;
	}
	public static void shell(int [] nums,int gap) {
		for(int i=gap;i<nums.length;i++) {
			int temp=nums[i];
			int j=i-gap;
			for(;j>=0;j-=gap) {
				if(nums[j]>temp) {
					nums[j+gap]=nums[j];
				} else {
					break;
				}
			}
			//这里防止j走到后面发生交换，j为-1，将temp的值给换回来。
			nums[j+gap]=temp;
		}
	}
	public static void main33(String[] args) {
		Random rand = new Random();
		//左闭右开
		int num=rand.nextInt(100);
		System.out.println();
		int [] nums=new int[num];
		int[] copy = Arrays.copyOf(nums, 10);
	}
	public static void main32(String[] args) {
		String str="abcdefghijklmnopqrstuvwxyz";
		StringBuilder stringBuilder=new StringBuilder();
		stringBuilder.append(str);
		//System.out.println(new String(stringBuilder));
		System.out.println(stringBuilder.append("97").toString());
	}
	public static void main31(String[] args) {
		LinkedList<Character> queue = new LinkedList<>();
		String str="bcabc";
		for(int i=0;i<str.length();i++){
			char ch=str.charAt(i);
			queue.add(ch);
		}
		Character ch = str.charAt(0);
		ch.equals('b');
		String part1=new String(queue.toString());
		System.out.println(part1);
		System.out.println(new String(queue.toString()));
	}
	public static void main30(String[] args) {
		int sum=0;
		int temp=38;
		while(temp>9) {
			int n=size(temp);
			while(n>0) {
				sum+=temp%10;
				temp/=10;
				n--;
			}
			temp=sum;
		}
		System.out.println(temp);
	}

	private static int size(int temp) {
		int ret=0;
		while(temp>0) {
			temp/=10;
			ret++;
		}
		return ret;
	}
	public static void main27(String[] args) {
		//[1,3],[2,6],[8,10],[15,18]
		List<Integer> list=new ArrayList<>();
		PriorityBlockingQueue<Integer> pq=new PriorityBlockingQueue<>();
		List<Integer> list2=new ArrayList<>();
		int num1=10;
		Map<String,Integer> map=new HashMap<>();
		int sum ='a'-'b';
	}
	public static void main28(String[] args) {
		int [][] nums=new int[][]{{1,3},{2,6},{8,10},{15,18}};
		Arrays.sort(nums,new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0]-o2[0];
			}
		});
		for(int i = 0;i<nums.length;i++){
			System.out.println(nums[i][0]);
		}
	}
	public static void main26(String[] args) {
		System.out.println();
	}
	public static void main25(String[] args) {
		String stones="aAAbbbb";
		Set<Character> set=new HashSet<>();
		for(char ch:stones.toCharArray()){

		}
	}
	public static void main24(String[] args) {
		int [] nums=new int []{3,0,1};
		Arrays.sort(nums);
		System.out.println(Arrays.toString(nums));
	}
	public static void main23(String[] args) {
		int x=2147483647;
		int target=(int) Math.floor(Math.sqrt(x));//46340
		int ret=0;
		for(int i =46340;i<=target+1;i++) {
			if(i*i==x) {
				ret=i;
				break;
			}
			if(i*i>x) {
				ret=i-1;
				break;
			}
		}
		System.out.println(ret);
	}
	public static void main22(String[] args) {
		String str="  hello world  ";
		System.out.println("之前"+str.length());
		String trimmed = str.trim();
		System.out.println(trimmed.length());
		System.out.println(trimmed);
		List<Integer>list=new ArrayList<>();
		list.add(1);
		Integer[] array =(Integer[]) list.toArray();
	}
	public static void main21(String[] args) {
		//二级缓存的问题
		//使用一个哈希表，然后里面的类型的是一个entry
		PriorityQueue<Map.Entry<Integer,Long>> queue = new PriorityQueue<>(((o1, o2) ->
				o1.getValue().compareTo(o2.getValue())));
		HashMap<Integer,Long> map = new HashMap<>(5);
		map.size();
		queue.size();
	}
	public static void main20(String[] args) {
		String str1="1432219";
	}
	public static void main19(String[] args) {
		int leftHeight=Integer.MAX_VALUE;
	}
	public static void main18(String[] args) {
		HashMap<Character,Integer> map=new HashMap<>();
		String s="()[]{}";
		for(int i=0;i<s.length();i++) {
			char ch = s.charAt(i);
			if (ch == '(' || ch == ')') {
				map.put('(', map.getOrDefault(ch, 0) + 1);
			}
			if (ch == '[' || ch == ']') {
				map.put('[', map.getOrDefault(ch, 0) + 1);
			}
			if (ch == '{' || ch == '}') {
				map.put('{', map.getOrDefault(ch, 0) + 1);
			}
		}
		for(Map.Entry<Character,Integer> entry:map.entrySet()) {
			System.out.println(entry.getKey()+" "+entry.getValue());
		}
	}
	public static void main17(String[] args) {
		int [] nums=new int []{3,3,3,4,5,7};
		HashMap<Integer,Integer> map=new HashMap<>();
		for(int i=0;i<nums.length;i++) {
			map.put(nums[i],map.getOrDefault(nums[i],0)+1);
		}
		for(Map.Entry<Integer,Integer> entry:map.entrySet()) {
			if(entry.getValue()>1)
			{
				System.out.println(entry.getKey()+" "+entry.getValue());
			}
		}
	}
	public static void main16(String[] args) {
		String str1="abcde";
		String str2="abcdef";
		int ret=0;
		ret^='a';
		System.out.println((char)ret);
		int [] nums=new int[26];
	}
	public static void main15(String[] args) {
		Queue<Integer> que=new LinkedList<>();
		List<Integer> list=new ArrayList<>();
		list.add(1);
		list.add(2);
		list.add(3);
		Collections.reverse(list);
		System.out.println(list);
	}
	public static void main14(String[] args) {
		int [] nums=new int []{11,11,11,11,11,66,11};
		int num=nums[0];
		for(int i=1;i<nums.length;i++){
			num^=nums[i];
		}
		System.out.println(num);
	}
	public static void main13(String[] args) {
		int [] nums = new int [10];
		HashMap<Integer,Integer> map = new HashMap();
	}
	public static void main12(String[] args) {
		Queue<Integer> queue = new LinkedList<Integer>();
		List<List<Integer>> ret = new ArrayList<List<Integer>>();
		List<Integer> list=new ArrayList<>();
		list.add(1);
		list.add(2);
		list.add(3);
		ret.add(list);
		List<Integer> list1=new ArrayList<>();
		list1.add(10);
		ret.add(list1);
		for(int i=0;i<ret.size();i++){
			System.out.println(ret.get(i).get(ret.get(i).size()-1));
		}
 	}
	//多位的水仙花数进行求解
	public static void main1(String[] args) {
		for (int i = 1; i < 999999; i++) {
			int temp = i;
			int cnt = 0;
			while (temp != 0) {
				temp /= 10;
				cnt++;
			}
			//位数拿到了
			temp = i;
			int sum = 0;
			while (temp != 0) {
				sum += Math.pow(temp % 10, cnt);
				//后面是要乘几次方，前面是数字
				temp /= 10;
			}
			if (sum == i) {
				System.out.println(i + "是水仙花数");
			}
		}
	}

	public static void main2(String[] args) {
		//打印1000以内的素数
		for (int i = 1; i <= 1000; i++) {
			int j = 2;
			for (; j < Math.sqrt(i); j++) {
				if (i % j == 0) {
					break;
				}
			}
			if (j > Math.sqrt(i)) {
				System.out.println(i + "是素数");
			}
		}
	}

	public static void main3(String[] args) {
		//打印图形
		//打印图形是有规律的，直接两层循环一套，然后计算之间有什么关系就行了
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i == j) {
					System.out.print("*");
				} else if (i + j == 4) {
					System.out.print("*");
				} else {
					System.out.print(" ");
				}
			}
			System.out.println();
		}
	}

	public static void main6(String[] args) {
		Scanner scaner = new Scanner(System.in);
		int cnt = 3;
		while (cnt != 0) {
			System.out.println("你还有" + cnt + "机会,请开始输入密码");
//			scaner.nextLine();//用来读取回车
			String s1 = scaner.next();
			if (s1.equals("123456")) {
				System.out.println("登录成功");
				break;
			} else {
				System.out.println("密码错误");
				cnt--;
			}
		}

	}

	public static void main5(String[] args) {
		//最大公约数
		int a=18;
		int b=24;
		int c=a%b;
		while(c!=0) {
			a=b;
			b=c;
			c=a%b;
		}
		System.out.println(b);
	}

	public static void main4(String[] args) {
		//打印一个数字的二进制序列奇数和偶数序列
		int b=7;
		for(int i = 31;i>=0;i-=2) {
			//从右往左开始打印
			//从左开始的话。让i加起来
			System.out.print(+((b>>i)&1)+" ");
		}
		System.out.println();
		for(int i = 30;i>=0;i-=2) {
			//从右往左开始打印
			//从左开始的话。让i加起来
			System.out.print(+((b>>i)&1)+" ");
		}
	}
}